package algorithm.model;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Antony
 * @Since 2018/7/19 19:52
 */
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) {val = x;}

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }

    /**
     * 根据数组，构建一个Tree,
     * 数组按BFS的方式，其中一级如果没有值，则需要置为null
     * @param nodeValues
     * @return
     */
    public static TreeNode getTreeNode(Integer[] nodeValues){
        if(nodeValues == null || nodeValues.length==0){
            return null;
        }
        TreeNode root = new TreeNode(nodeValues[0]);
        List<TreeNode> preLevelNodes = new ArrayList<>();
        List<TreeNode> currLevelNodes = new ArrayList<>(2);
        preLevelNodes.add(root);

        int length = nodeValues.length;
        int point = 1;

        int levelSize = 2;
        int tmpIdx = 0;

        while(point < length){
            if(tmpIdx == levelSize){
                tmpIdx=0;
                levelSize = currLevelNodes.size() *2;
                preLevelNodes = currLevelNodes;
                currLevelNodes = new ArrayList<>(levelSize);
                continue;
            }

            Integer val = nodeValues[point++];
            if(val != null){
                TreeNode node = new TreeNode(val);
                currLevelNodes.add(node);
                TreeNode parent = preLevelNodes.get(tmpIdx/2);
                if(tmpIdx%2==0){
                    parent.left = node;
                }else{
                    parent.right = node;
                }
            }
            tmpIdx++;
        }

        return root;
    }


    public static void main(String[] args) {
        Integer[] vals = new Integer[]{5,4,8,11,null,13,4,7,2,null,null,null,1};
        TreeNode root = TreeNode.getTreeNode(vals);
        System.out.println(root);

        TreeNode node1 = TreeNode.getTreeNode(new Integer[]{1,null,2,null,3,null,4,null,5});
        System.out.println(node1);
    }

}
